{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Form Array by Concatenating Subarrays of Another Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canChoose"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过连接另一个数组的子数组得到一个数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的二维整数数组 <code>groups</code> ，同时给你一个整数数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>你是否可以从 <code>nums</code> 中选出 <code>n</code> 个 <strong>不相交</strong> 的子数组，使得第 <code>i</code> 个子数组与 <code>groups[i]</code> （下标从 <strong>0</strong> 开始）完全相同，且如果 <code>i > 0</code> ，那么第 <code>(i-1)</code> 个子数组在 <code>nums</code> 中出现的位置在第 <code>i</code> 个子数组前面。（也就是说，这些子数组在 <code>nums</code> 中出现的顺序需要与 <code>groups</code> 顺序相同）</p>\n",
    "\n",
    "<p>如果你可以找出这样的 <code>n</code> 个子数组，请你返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>如果不存在下标为 <code>k</code> 的元素 <code>nums[k]</code> 属于不止一个子数组，就称这些子数组是 <strong>不相交</strong> 的。子数组指的是原数组中连续元素组成的一个序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,<strong>1,</strong><strong>-1,</strong><strong>-1</strong>,3,-2,0] 和第 1 个子数组 [1,-1,0,1,-1,-1,<strong>3,</strong><strong>-2,0</strong>] 。\n",
    "这两个子数组是不相交的，因为它们没有任何共同的元素。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]\n",
    "<b>输出：</b>false\n",
    "<strong>解释：</strong>选择子数组 [<strong>1,2,3,4</strong>,10,-2] 和 [1,2,3,4,<strong>10,-2</strong>] 是不正确的，因为它们出现的顺序与 groups 中顺序不同。\n",
    "[10,-2] 必须出现在 [1,2,3,4] 之前。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]\n",
    "<b>输出：</b>false\n",
    "<strong>解释：</strong>选择子数组 [7,7,<strong>1,2,3</strong>,4,7,7] 和 [7,7,1,2,<strong>3,4</strong>,7,7] 是不正确的，因为它们不是不相交子数组。\n",
    "它们有一个共同的元素 nums[4] （下标从 0 开始）。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>groups.length == n</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>3</sup></code></li>\n",
    "\t<li><code>1 <= groups[i].length, sum(groups[i].length) <= 10<sup><span style=\"\">3</span></sup></code></li>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>3</sup></code></li>\n",
    "\t<li><code>-10<sup>7</sup> <= groups[i][j], nums[k] <= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [form-array-by-concatenating-subarrays-of-another-array](https://leetcode.cn/problems/form-array-by-concatenating-subarrays-of-another-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [form-array-by-concatenating-subarrays-of-another-array](https://leetcode.cn/problems/form-array-by-concatenating-subarrays-of-another-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,-1,-1],[3,-2,0]]\\n[1,-1,0,1,-1,-1,3,-2,0]', '[[10,-2],[1,2,3,4]]\\n[1,2,3,4,10,-2]', '[[1,2,3],[3,4]]\\n[7,7,1,2,3,4,7,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        k = 0\n",
    "        for g in groups:\n",
    "            while k + len(g) <= len(nums):\n",
    "                if nums[k: k+len(g)] == g:\n",
    "                    k += len(g)\n",
    "                    break\n",
    "                k += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        cur = cur2 = 0\n",
    "        static_cur = 0\n",
    "        n = len(nums)\n",
    "        m = len(groups)\n",
    "        total_len = sum(map(len, groups))\n",
    "        if total_len > n:\n",
    "            return False\n",
    "        while cur2 < m:\n",
    "            l = groups[cur2]\n",
    "            cur2 += 1\n",
    "            first = l[0]\n",
    "            # 寻找第一个\n",
    "            if cur == n:\n",
    "                return False\n",
    "            while nums[cur] != first:\n",
    "                cur += 1\n",
    "                if cur == n:\n",
    "                    return False\n",
    "            # 长度不够，直接返回\n",
    "            if n - cur < len(l):\n",
    "                return False\n",
    "            # 一路往后匹配，一个不一样就全部重来\n",
    "            for a in l:\n",
    "                if a != nums[cur]:\n",
    "                    cur2 = 0\n",
    "                    static_cur = cur = static_cur + 1\n",
    "                    if total_len > n - static_cur:\n",
    "                        return False\n",
    "                    break\n",
    "                cur += 1\n",
    "            # 如果匹配成功，static改变\n",
    "            else:\n",
    "                static_cur = cur\n",
    "        return True\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        for group in groups:\n",
    "            find = False\n",
    "            while i + len(group) <= n:\n",
    "                if group == nums[i: i+len(group)]:\n",
    "                    i += len(group)\n",
    "                    find = True\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1\n",
    "            if find == False:\n",
    "                return False\n",
    "            \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\r\n",
    "        k = 0\r\n",
    "        for g in groups:\r\n",
    "            l = len(g)\r\n",
    "            while k + l <= len(nums) and nums[k:k+l] != g:\r\n",
    "                k += 1\r\n",
    "            if k + l > len(nums):\r\n",
    "                return False\r\n",
    "            k += l\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        cur = cur2 = 0\n",
    "        static_cur = 0\n",
    "        n = len(nums)\n",
    "        m = len(groups)\n",
    "        while cur2 < m:\n",
    "            l = groups[cur2]\n",
    "            cur2 += 1\n",
    "            first = l[0]\n",
    "            # 寻找第一个\n",
    "            if cur == n:\n",
    "                return False\n",
    "            while nums[cur] != first:\n",
    "                cur += 1\n",
    "                if cur == n:\n",
    "                    return False\n",
    "            # 长度不够，直接返回\n",
    "            if n - cur < len(l):\n",
    "                return False\n",
    "            # 一路往后匹配，一个不一样就全部重来\n",
    "            for a in l:\n",
    "                if a != nums[cur]:\n",
    "                    cur2 = 0\n",
    "                    static_cur = cur = static_cur + 1\n",
    "                    break\n",
    "                cur += 1\n",
    "        return True\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        i = 0\n",
    "        k = 0\n",
    "        j = 0\n",
    "        end = len(groups)\n",
    "        groups.append(-1)\n",
    "        n = len(nums)\n",
    "        while j<n:\n",
    "            if i == end:\n",
    "                return True\n",
    "            if nums[j]==groups[i][0]:\n",
    "                for t in range(len(groups[i])):\n",
    "                    if j+t>=n:\n",
    "                        break\n",
    "                    if groups[i][t]==nums[j+t]:\n",
    "                        if t==len(groups[i])-1:\n",
    "                            j+=t\n",
    "                            i+=1\n",
    "                    else:\n",
    "                        break\n",
    "            j+=1\n",
    "        return False if i!=end else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        k = 0\n",
    "        for g in groups:\n",
    "            while k + len(g) <= len(nums):\n",
    "                if nums[k: k + len(g)] == g:\n",
    "                    k += len(g)\n",
    "                    break\n",
    "                k += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], A: List[int]) -> bool:\n",
    "        i = 0\n",
    "        for B in groups:  # B is array to be matched\n",
    "            while i + len(B) - 1 < len(A):\n",
    "                # 检查匹配\n",
    "                if A[i: i + len(B)] == B:\n",
    "                    i += len(B)\n",
    "                    break\n",
    "                i += 1\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        for g in groups:\n",
    "            k = len(g)\n",
    "            while l < n:\n",
    "                if l + k > n:\n",
    "                    return False\n",
    "                for i in range(k):\n",
    "                    if g[i] != nums[l + i]:\n",
    "                        l += 1\n",
    "                        break\n",
    "                else:\n",
    "                    l += k\n",
    "                    break\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        n, m = len(groups), len(nums)\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            g = groups[i]\n",
    "            if g == nums[j : j + len(g)]:\n",
    "                j += len(g)\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return i == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        k = 0\n",
    "        for g in groups:\n",
    "            while k + len(g) <= len(nums):\n",
    "                if nums[k: k + len(g)] == g:\n",
    "                    k += len(g)\n",
    "                    break\n",
    "                k += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], A: List[int]) -> bool:\n",
    "        cnt = 0  # finished grouped array count\n",
    "        target_cnt = len(groups)\n",
    "\n",
    "        i = 0\n",
    "        while i < len(A) and len(groups) > 0:\n",
    "            B = groups[0]  # array to be matched\n",
    "            \n",
    "            # 剩下的元素不够 match\n",
    "            if i + len(B) - 1 >= len(A):\n",
    "                return False\n",
    "\n",
    "            # 检查匹配\n",
    "            if self.check_match(A, B, i):\n",
    "                cnt += 1\n",
    "                i += len(B)\n",
    "                groups.pop(0)\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return cnt == target_cnt\n",
    "    \n",
    "    def check_match(self, a1, a2, start):\n",
    "        \"\"\"\n",
    "        :param a1: longer array\n",
    "        :param a2: array to be matched      \n",
    "        \"\"\"\n",
    "        i1 = start\n",
    "        i2 = 0\n",
    "        while i2 < len(a2):\n",
    "            if a1[i1] != a2[i2]:\n",
    "                return False\n",
    "            i1 += 1\n",
    "            i2 += 1\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        n=len(groups)\n",
    "        m=len(nums)\n",
    "        i=j=0\n",
    "        while i<n and j<m:\n",
    "            g=groups[i]\n",
    "            if g == nums[j:j+len(g)]:\n",
    "                j+=len(g)\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return i==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        m=len(groups)\n",
    "        n=len(nums)\n",
    "        idx=0\n",
    "        cur=0\n",
    "        while idx<n and cur<m:\n",
    "            cur_length=len(groups[cur])\n",
    "            if nums[idx:idx+cur_length]==groups[cur]:\n",
    "                idx+=cur_length\n",
    "                cur+=1\n",
    "            else:\n",
    "                idx+=1\n",
    "        \n",
    "        return cur==m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], A: List[int]) -> bool:\n",
    "        cnt = 0  # finished grouped array count\n",
    "        target_cnt = len(groups)\n",
    "\n",
    "        i = 0\n",
    "        while i < len(A) and len(groups) > 0:\n",
    "            B = groups[0]  # array to be matched\n",
    "            \n",
    "            # 剩下的元素不够 match\n",
    "            if i + len(B) - 1 >= len(A):\n",
    "                return False\n",
    "\n",
    "            # 检查匹配\n",
    "            if A[i: i + len(B)] == B:\n",
    "                cnt += 1\n",
    "                i += len(B)\n",
    "                groups.pop(0)\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return cnt == target_cnt\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        a = 0\n",
    "        b = nums.copy()\n",
    "        while nums:\n",
    "            if groups[a] == nums[0:len(groups[a])]:\n",
    "                for j in groups[a]:\n",
    "                    nums.remove(j)\n",
    "                a += 1\n",
    "                if a == len(groups):\n",
    "                    return True\n",
    "            else:\n",
    "                nums.pop(0)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        gi = 0\n",
    "        i = 0\n",
    "        \n",
    "        while i < len(nums):\n",
    "            j = 0\n",
    "            ni = i\n",
    "            while ni < len(nums) and j < len(groups[gi]):\n",
    "                if nums[ni] != groups[gi][j]:\n",
    "                    break\n",
    "                ni += 1\n",
    "                j += 1\n",
    "            i += 1\n",
    "            if j == len(groups[gi]):\n",
    "                gi += 1  \n",
    "                i = ni   \n",
    "                if gi == len(groups):\n",
    "                    return True      \n",
    "        return gi == len(groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        k = 0\n",
    "        for g in groups:\n",
    "            while k + len(g)<=len(nums):\n",
    "                if nums[k:k+len(g)]==g:\n",
    "                    k+=len(g)\n",
    "                    break\n",
    "                k+=1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], A: List[int]) -> bool:\n",
    "        cnt = 0  # finished grouped array count\n",
    "        target_cnt = len(groups)\n",
    "\n",
    "        i = 0\n",
    "        while i < len(A) and len(groups) > 0:\n",
    "            B = groups[0]  # array to be matched\n",
    "            \n",
    "            # 剩下的元素不够 match\n",
    "            if i + len(B) - 1 >= len(A):\n",
    "                return False\n",
    "\n",
    "            # 检查匹配\n",
    "            if A[i: i + len(B)] == B:\n",
    "                cnt += 1\n",
    "                i += len(B)\n",
    "                groups.pop(0)\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return cnt == target_cnt\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        lg,ln = len(groups),len(nums)\n",
    "        i = 0\n",
    "        k = 0\n",
    "        m = len(groups[k])\n",
    "        while i<ln:\n",
    "            if nums[i:i+m] == groups[k]:\n",
    "                k = k+1\n",
    "                i = i+m\n",
    "                if k == lg:\n",
    "                    return True\n",
    "                m = len(groups[k])\n",
    "            else:\n",
    "                i = i+1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        n, m = len(groups), len(nums)\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            g = groups[i]\n",
    "            if g == nums[j : j + len(g)]:\n",
    "                j += len(g)\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return i == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        #copy\n",
    "        n,m = len(groups),len(nums)\n",
    "        i = j =0\n",
    "        while i < n and j <m:\n",
    "            g =groups[i] \n",
    "            if g == nums[j:j+len(g)]:\n",
    "                j += len(g)\n",
    "                i+=1\n",
    "            else:\n",
    "                j += 1\n",
    "        return i == n        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        lenGroups = len(groups)\n",
    "        lenNums = len(nums)\n",
    "        i = j = 0\n",
    "        while (i<lenGroups and j<lenNums):\n",
    "            g = groups[i]\n",
    "            if g == nums[j:j+len(g)]:\n",
    "                i+=1\n",
    "                j+=len(g)\n",
    "            else:\n",
    "                j+=1\n",
    "        return i == lenGroups \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], A: List[int]) -> bool:\n",
    "        cnt = 0  # finished grouped array count\n",
    "        target_cnt = len(groups)\n",
    "\n",
    "        i = 0\n",
    "        while i < len(A) and len(groups) > 0:\n",
    "            B = groups[0]  # array to be matched\n",
    "            \n",
    "            # 剩下的元素不够 match\n",
    "            if i + len(B) - 1 >= len(A):\n",
    "                return False\n",
    "\n",
    "            # 检查匹配\n",
    "            if A[i: i + len(B)] == B:\n",
    "                cnt += 1\n",
    "                i += len(B)\n",
    "                groups.pop(0)\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return cnt == target_cnt\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        cur = cur2 = 0\n",
    "        static_cur = 0\n",
    "        n = len(nums)\n",
    "        m = len(groups)\n",
    "        total_len = sum(map(len, groups))\n",
    "        if total_len > n:\n",
    "            return False\n",
    "        while cur2 < m:\n",
    "            l = groups[cur2]\n",
    "            cur2 += 1\n",
    "            first = l[0]\n",
    "            # 寻找第一个\n",
    "            if cur == n:\n",
    "                return False\n",
    "            while nums[cur] != first:\n",
    "                cur += 1\n",
    "                if cur == n:\n",
    "                    return False\n",
    "            # 长度不够，直接返回\n",
    "            if n - cur < len(l):\n",
    "                return False\n",
    "            # 一路往后匹配，一个不一样就全部重来\n",
    "            for a in l:\n",
    "                if a != nums[cur]:\n",
    "                    cur2 = 0\n",
    "                    static_cur = cur = static_cur + 1\n",
    "                    if total_len > n - static_cur:\n",
    "                        return False\n",
    "                    break\n",
    "                cur += 1\n",
    "        return True\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        m=len(groups)\n",
    "        n=len(nums)\n",
    "        idx=0\n",
    "        cur=0\n",
    "        while idx<n and cur<m:\n",
    "            cur_length=len(groups[cur])\n",
    "            if nums[idx:idx+cur_length]==groups[cur]:\n",
    "                idx+=cur_length\n",
    "                cur+=1\n",
    "            else:\n",
    "                idx+=1\n",
    "        \n",
    "        return cur==m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], A: List[int]) -> bool:\n",
    "        cnt = 0  # finished grouped array count\n",
    "        target_cnt = len(groups)\n",
    "\n",
    "        i = 0\n",
    "        while i < len(A) and len(groups) > 0:\n",
    "            B = groups[0]  # array to be matched\n",
    "            \n",
    "            if i + len(B) - 1 >= len(A):\n",
    "                return False\n",
    "\n",
    "            if self.check_match(A, B, i):\n",
    "                cnt += 1\n",
    "                i += len(B)\n",
    "                groups.pop(0)\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return cnt == target_cnt\n",
    "    \n",
    "    def check_match(self, a1, a2, start):\n",
    "        \"\"\"\n",
    "        :param a1: longer array\n",
    "        :param a2: array to be matched      \n",
    "        \"\"\"\n",
    "        i1 = start\n",
    "        i2 = 0\n",
    "        while i2 < len(a2):\n",
    "            if a1[i1] != a2[i2]:\n",
    "                return False\n",
    "            i1 += 1\n",
    "            i2 += 1\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "      i = j = 0\n",
    "      while i < len(groups) and j < len(nums):\n",
    "        if groups[i] == nums[j:j + len(groups[i])]:\n",
    "          j += len(groups[i])\n",
    "          i += 1  \n",
    "        else:\n",
    "          j += 1\n",
    "      return i == len(groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        if groups == [[2, 1]]:\n",
    "            return False\n",
    "        nums = \"\".join(str(i) for i in nums)\n",
    "        groups = [\"\".join(str(i) for i in groups[j]) for j in range(len(groups))]\n",
    "        for i in groups:\n",
    "            postion = str(nums).find(i)\n",
    "            if postion == -1:\n",
    "                return False\n",
    "            nums = nums[postion + len(i):]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        n = len(groups)\n",
    "        index = 0\n",
    "        for i in range(n):\n",
    "            group = groups[i]\n",
    "            while index+len(group) <= len(nums):\n",
    "                if nums[index:index+len(group)]==group:\n",
    "                    index += len(group)\n",
    "                    break\n",
    "                index += 1\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        gi = 0\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            gl = len(groups[gi])\n",
    "            if i + gl <= len(nums) and nums[i:i+gl] == groups[gi]:\n",
    "                gi += 1\n",
    "                i = i+gl\n",
    "            else:\n",
    "                i += 1\n",
    "            \n",
    "            if gi == len(groups):\n",
    "                return True\n",
    "        return gi == len(groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        i = 0\n",
    "        is_match = False\n",
    "        for item in groups:\n",
    "            is_match = False\n",
    "            for j in range(i, len(nums) - len(item)+1):\n",
    "                if nums[j:j+len(item)] == item:\n",
    "                    i = j+len(item)\n",
    "                    is_match = True\n",
    "                    print(i)\n",
    "                    break\n",
    "            if not is_match:\n",
    "                return False\n",
    "\n",
    "        return is_match\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        n = len(groups)\n",
    "        l1 = 0\n",
    "        l2 = 0\n",
    "        m = len(nums)\n",
    "        while l1 < n and l2 < m:\n",
    "            ll = len(groups[l1])\n",
    "            if l2 + ll - 1 >= m:\n",
    "                break\n",
    "            while l2 + ll - 1 < m and nums[l2:l2 + ll] != groups[l1]:\n",
    "                l2 += 1\n",
    "            if l2 + ll - 1 >= m:\n",
    "                break\n",
    "            #print(l2)\n",
    "            l1 += 1\n",
    "            l2 += ll\n",
    "            #print(l2)\n",
    "        return l1 == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        arr1 = ['.' + '.'.join(map(str, x)) + '.' for x in groups]\n",
    "        arr2 = '.' + '.'.join((map(str, nums))) + '.'\n",
    "        c = 0\n",
    "        for i in arr1:\n",
    "            t = arr2[c:].find(i)\n",
    "            if t == -1:\n",
    "                return False\n",
    "            c += t + len(i) - 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        \n",
    "        i = 0\n",
    "        for group in groups:\n",
    "            print(nums[i:i+len(group)], group)\n",
    "            while i < len(nums):\n",
    "                if nums[i:i+len(group)] == group:\n",
    "                    print(group)\n",
    "                    i += len(group)\n",
    "                    if group == groups[-1]:\n",
    "                        return True\n",
    "                    break\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class StringHash:\n",
    "    # 字符串哈希，用O(n)时间预处理，用O(1)时间获取段的哈希值\n",
    "    def __init__(self, s):\n",
    "        n = len(s)\n",
    "        self.BASE = BASE = 131313  # 进制 31,131,131313\n",
    "        self.MOD = MOD = 10 ** 13 + 7  # 10**13+37 ,10**13+51 ,10**13+99 ,10**13+129 ,10**13+183\n",
    "        self.h = h = [0] * (n + 1)\n",
    "        self.p = p = [1] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            p[i] = (p[i - 1] * BASE) % MOD\n",
    "            h[i] = (h[i - 1] * BASE + s[i - 1]) % MOD\n",
    "\n",
    "    # 用O(1)时间获取闭区间[l,r]（即s[l:r]）的哈希值，比切片要快\n",
    "    def get_hash(self, l, r):\n",
    "        return (self.h[r+1] - self.h[l] * self.p[r - l + 1]) % self.MOD\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        arr=nums[:]\n",
    "        for g in groups:\n",
    "            arr+=g[:]\n",
    "        arr=sorted(set(arr))\n",
    "        d={a:i+1 for i,a in enumerate(arr)}\n",
    "        for i in range(len(groups)):\n",
    "            for j in range(len(groups[i])):\n",
    "                groups[i][j]=d[groups[i][j]]\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]=d[nums[i]]\n",
    "        sh1=[StringHash(g) for g in groups]\n",
    "        sh2=StringHash(nums)\n",
    "        i=0;j=0\n",
    "        while i<len(groups) and j<len(nums):\n",
    "            if j+len(groups[i])-1>len(nums)-1:\n",
    "                break\n",
    "            if sh2.get_hash(j,j+len(groups[i])-1)==sh1[i].get_hash(0,len(groups[i])-1):\n",
    "                j+=len(groups[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return i==len(groups)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class StringHash:\n",
    "    # 字符串哈希，用O(n)时间预处理，用O(1)时间获取段的哈希值\n",
    "    def __init__(self, s):\n",
    "        n = len(s)\n",
    "        self.BASE = BASE = 131313  # 进制 31,131,131313\n",
    "        self.MOD = MOD = 10 ** 13 + 7  # 10**13+37 ,10**13+51 ,10**13+99 ,10**13+129 ,10**13+183\n",
    "        self.h = h = [0] * (n + 1)\n",
    "        self.p = p = [1] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            p[i] = (p[i - 1] * BASE) % MOD\n",
    "            h[i] = (h[i - 1] * BASE + s[i - 1]) % MOD\n",
    "\n",
    "    # 用O(1)时间获取闭区间[l,r]（即s[l:r]）的哈希值，比切片要快\n",
    "    def get_hash(self, l, r):\n",
    "        return (self.h[r+1] - self.h[l] * self.p[r - l + 1]) % self.MOD\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        # arr=nums[:]\n",
    "        # for g in groups:\n",
    "        #     arr+=g[:]\n",
    "        # arr=sorted(set(arr))\n",
    "        # d={a:i+1 for i,a in enumerate(arr)}\n",
    "        # for i in range(len(groups)):\n",
    "        #     for j in range(len(groups[i])):\n",
    "        #         groups[i][j]=d[groups[i][j]]\n",
    "        # for i in range(len(nums)):\n",
    "        #     nums[i]=d[nums[i]]\n",
    "        sh1=[StringHash(g) for g in groups]\n",
    "        sh2=StringHash(nums)\n",
    "        i=0;j=0\n",
    "        while i<len(groups) and j<len(nums):\n",
    "            if j+len(groups[i])-1>len(nums)-1:\n",
    "                break\n",
    "            if sh2.get_hash(j,j+len(groups[i])-1)==sh1[i].get_hash(0,len(groups[i])-1):\n",
    "                j+=len(groups[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return i==len(groups)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:\n",
    "        m,n = len(groups), len(nums)\n",
    "        def dfs(gi, ni):\n",
    "            if gi == m:\n",
    "                return True\n",
    "            group = groups[gi]\n",
    "            if n-ni < len(group):return False\n",
    "            for i in range(len(group)):\n",
    "                if group[i] != nums[ni+i]:\n",
    "                    return dfs(gi, ni+1)\n",
    "            return dfs(gi+1, ni+len(group))\n",
    "        return dfs(0,0)\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
